%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input
\Require A nonempty list $L$ of positive integers. Elements of $L$ are
  sorted in nondecreasing order. An integer $i$ for which we want to
  search in $L$.
\Ensure \MyTrue if $i$ is in $L$; \MyFalse otherwise.
%%
%% algorithm body
\State $\MyLow \gets 0$
\State $\MyHigh \gets |L| - 1$
\While{$\MyLow \leq \MyHigh$}
  \State $\MyMid \gets \lfloor\frac{\MyLow\, +\, \MyHigh}{2}\rfloor$\label{alg:binary_search:mid_floor}
  \If{$i = L[\MyMid]$}
    \State \Return \MyTrue
  \EndIf
  \If{$i < L[\MyMid]$}
    \State $\MyHigh \gets \MyMid - 1$
  \Else
    \State $\MyLow \gets \MyMid + 1$
  \EndIf
\EndWhile
\State \Return \MyFalse
\end{algorithmic}
